package cn.edu.njust.alg.leetcode;

import java.util.ArrayList;
import java.util.List;

public class Leetcode_119_pascalstriangle {

	/*
	 * Given an index k, return the kth row of the Pascal's triangle.
	 * 
	 * For example, given k = 3, Return [1,3,3,1].
	 * 
	 * Note: Could you optimize your algorithm to use only O(k) extra space?
	 */
	public List<Integer> getRow(int rowIndex) {

		return null;
	}

	public List<Integer> generate(int numRows) {

		List<List<Integer>> pascals = new ArrayList<List<Integer>>();
		if (numRows <= 0) {
			List<Integer> list= new ArrayList<Integer>();
			list.add(1);
			return list;
		}
		List<Integer> list = new ArrayList<Integer>();
		list.add(1);
		pascals.add(list);

		for (int i = 1; i <= numRows; i++) {
			list = new ArrayList<Integer>();
			List<Integer> prelist = pascals.get(i - 1);
			list.add(1);
			for (int j = 1; j < prelist.size(); j++) {
				int s = prelist.get(j - 1) + prelist.get(j);
				list.add(s);
			}
			list.add(1);
			pascals.add(list);
		}

		return pascals.get(numRows);
	}

	public static void main(String[] args) {
		List<Integer> pascals = new Leetcode_119_pascalstriangle().generate(2);
		System.out.println("[");
		for (Integer i : pascals) {
			System.out.print("[");

			System.out.print(i + " ");

			System.out.print("]");
		}
		System.out.println();
		System.out.println("]");

	}

}
